package vip.zhenzicheng.algorithm.leetcode.binary_tree;

import vip.zhenzicheng.algorithm.TreeNode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * <a href="https://leetcode.cn/problems/binary-tree-inorder-traversal/">二叉树中序遍历 [简单]</a>
 * 给定一个二叉树的根节点root，返回它的中序遍历
 * input:[1,null,2,3] -> output:[1,3,2]
 * 提示：
 * 树中节点数目在范围 [0, 100] 内
 * -100 <= Node.val <= 100
 * 进阶：不使用递归使用迭代
 *
 * @author zhenzicheng
 * @date 2022-06-04 12:40
 */
public class BinaryTreeInoderTraversal_94 {

  /**
   * 解法1：使用递归
   */
  // public List<Integer> inorderTraversal(TreeNode root) {
  //   List<Integer> res = new ArrayList<>();
  //   accessTree(root, res);
  //
  //   return res;
  // }
  //
  // public void accessTree(TreeNode root, List<Integer> res) {
  //   if (root == null) {
  //     return;
  //   }
  //
  //   accessTree(root.left, res); // 先访问左子树
  //   res.add(root.val); // 然后访问当前节点
  //   accessTree(root.right, res); // 最后访问右子树
  // }

  /**
   * 解法2：使用栈
   */
  public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>(); // 1.6新结构，或者使用1.2的LinkedList
    TreeNode cur = root; // 遍历的当前节点

    while (cur != null || !stack.isEmpty()) {
      // 压入左子树
      while (cur != null) {
        cur = cur.left;
        stack.push(cur);
      }
      cur = stack.pop(); // 弹出逻辑左节点
      res.add(cur.val);
      cur = cur.right;

    }

    return res;
  }

}
